#include "Heap.h"

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

//向下调整
//小堆向下调整前提:左右子树都为小堆
//大堆向下调整前提:左右子树都为大堆
void AdjustDown(HPDataType* a, int n, int root)
{
    int parent = root;//将根节点位置给父节点
    int child = 2 * parent + 1;//子节点下标为2*parent+1

    while (child < n)//保证下标不越界
    {
        //找出左右孩子小的那个
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }

        //若孩子的值小于父亲则交换,并将孩子下标给父亲,重新计算孩子下标
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        //如果孩子大,则说明为小堆,不需要向下调整
        else
        {
            break;
        }
    }
}

//向上调整
void AdjustUp(HPDataType* a, int n, int child)
{
    //已知子节点下标,则父节点为(child-1/)2
    int parent = (child - 1) / 2;

    while (child > 0)
    {

        if (child < n && a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

//初始化
void HeapInit(Heap* php, HPDataType* a, int n)
{
    php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if (php->_a == NULL)
        return;
    //将给定数组的内容复制
    memcpy(php->_a, a, sizeof(HPDataType) * n);
    php->_size = n;
    php->_capacity = n;

    //构建堆
    //n-1为最后一个节点下标,(n-1-1)/2为计算父节点下标公式
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(php->_a, php->_size, i);
    }
}

//堆排序
//1.升序建大堆,使用向下调整
//2.降序建小堆,使用向上调整
void HeapSort(int* a, int n)
{
    //建堆
    //假设树有N个节点,树高度:logN.时间复杂度:O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(a, n, i);//向下调整
    }

    int end = n - 1;//最后一个叶的下标
    while (end > 0)
    {
        Swap(&a[0], &a[end]);

        AdjustDown(a, end, 0);
        --end;
    }
}


//销毁
void HeapDistory(Heap* php)
{
    assert(php);

    free(php->_a);
    php->_a = NULL;
    php->_capacity = php->_size = 0;
}

//堆添加
void HeapPush(Heap* php, HPDataType x)
{
    assert(php);

    if (php->_size == php->_capacity)
    {
        php->_capacity *= 2;
        HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType));
        if (tmp == NULL)
            return;
        php->_a = tmp;
    }

    php->_a[php->_size++] = x;
    //php->_size++;
    AdjustUp(php->_a, php->_size, php->_size - 1);//向上调整

}

//堆删除
void HeapPop(Heap* php)
{
    assert(php);
    assert(php->_size > 0);

    Swap(&php->_a[0], &php->_a[php->_size - 1]);
    php->_size--;

    AdjustDown(php->_a, php->_size, 0);

}

//取堆顶元素
HPDataType HeapTop(Heap* php)
{
    assert(php);
    assert(php->_size > 0);

    return php->_a[0];
}

void HeapPrint(Heap* php)
{
    while (php->_size > 0)
    {
        printf("%d ", HeapTop(php));
        HeapPop(php);
    }
    printf("\n");
};